import java.util.Arrays;

public class FibonacciSearch {
	
	public static int FLENGTH = 20;
	public static void main(String[] args) {
		int [] arr = {1,8,10,89,100,134};
		int target = 89;
		System.out.println("目标元素在数组中位置是：" + fibSearch(arr, target));		
	}

	public static int[] fib() {
		int[] f = new int[FLENGTH];
		f[0] = 1;
		f[1] = 1;
		for (int i = 2; i < FLENGTH; i++) {
			f[i] = f[i-1] + f[i-2];
		}
		return f;
	}
	
	public static int fibSearch(int[] arr, int target) {
		int low = 0;
		int high = arr.length - 1;
		int k = 0; 
		int mid = 0; 
		int f[] = fib();
		/*获取最相邻的斐波那契数组中元素的值，该值略大于数组的长度*/
		while(high > f[k] - 1) {
			k++;
		}
		/*因为 f[k]值可能大于arr的长度。如果大于时，需要构造一个新的数组temp[]，将arr数组中的元素拷贝过去，不足的部分会使用0填充*/
		int[] temp= Arrays.copyOf(arr, f[k]);
		/*然后将temp后面填充的0，替换为最后一位数字
		 *如将temp数组由{1,8,10,89,100,134,0,0}变换为{1,8,10,89,100,134,134,134}*/
		for(int i = high + 1; i < temp.length; i++) {
			temp[i] = arr[high];
		}
		
		while (low <= high) { 
			mid = low + f[k - 1] - 1;
			if(target < temp[mid]) { 
				high = mid - 1;
				/*因为f[k]=f[k-1]+f[k-2]，所以k--就相当于取temp数组的左边部分*/
				k--;
			} else if ( target > temp[mid]) { 
				low = mid + 1;
				/*同理，f[k]=f[k-1]+f[k-2]，k -= 2就相当于取temp数组的右边部分*/
				k -= 2;
			} else {
				/*原arr数组中的值*/
				if(mid <= high){
					return mid;
				/*在temp中，扩展出来的高位的值*/
				}else{
					return high;
				}
			}
		}
		return -1;
	}
}
